package com.gitee.wsl.ext.array.sort

import com.gitee.wsl.ext.array.swap


/**
 * Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
 * Each iteration, insertion sort removes one element from the input data, finds the location it belongs within
 * the sorted list, and inserts it there. It repeats until no input elements remain.
 *
 * Worst-case performance:       O(n^2)
 * Best-case performance:        O(n)
 * Average performance:          O(n^2)
 * Worst-case space complexity:  O(1)
 */
fun<T : Comparable<T>> Array<T>.insertionSort(){
    for (i in 1 until size) {
        for (j in i downTo 1) {
            if (this[j - 1] < this[j]) {
                break
            }
            swap(j, j - 1)
        }
    }
}

/**
 * Implementation of the generic insertion sort algorithm.
 *
 * Worst-case performance:       O(n^2)
 * Best-case performance:        O(n)
 * Average performance:          O(n^2)
 * Worst-case space complexity:  O(1)
 */
fun<T : Comparable<T>> Array<T>.insertionSort2(){
    for (currentIndex in 1 until size) {
        val currentValue = this[currentIndex]
        var j = currentIndex
        while (j > 0 && this[j - 1] > currentValue) {
            this[j] = this[j - 1]
            j--
        }
        this[j] = currentValue
    }
}
